<!DOCTYPE html>


<html lang="zh-CN">


<head>
  <meta charset="utf-8" />
  <meta name="baidu-site-verification" content="code-kg5UjKJZM2" />
   
  <meta name="keywords" content="活,炼" />
   
  <meta name="description" content="shimmerjordan" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    The Framework of Backtracking Algorithm Problems (DFS) |  丛烨-shimmerjordan
  </title>
  <meta name="generator" content="hexo-theme-ayer">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/dist/main.css">

  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Shen-Yu/cdn/css/remixicon.min.css">
  
<link rel="stylesheet" href="/css/custom.css">

  
  <script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
  
  

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'G-Q0DT8B8VJW', 'auto');
ga('send', 'pageview');

</script>



  
<script>
var _hmt = _hmt || [];
(function() {
	var hm = document.createElement("script");
	hm.src = "https://hm.baidu.com/hm.js?6d06f826e125297d4ce0fa7a1449328e";
	var s = document.getElementsByTagName("script")[0]; 
	s.parentNode.insertBefore(hm, s);
})();
</script>


<link rel="alternate" href="/atom.xml" title="丛烨-shimmerjordan" type="application/atom+xml">
</head>

</html>

	<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">
	<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>


<body>
  <div id="app">
    
      
    <main class="content on">
      <section class="outer">
  <article
  id="post-DFSFramework"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  The Framework of Backtracking Algorithm Problems (DFS)
</h1>
 

    </header>
     
    <div class="article-meta">
      <a href="/2021/08/07/DFSFramework/" class="article-date">
  <time datetime="2021-08-06T16:00:12.000Z" itemprop="datePublished">2021-08-07</time>
</a> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/Algorithm/">Algorithm</a>
  </div>
  
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">2.3k</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">14 分钟</span>
        </span>
    </span>
</div>
 
    </div>
      
    <div class="tocbot"></div>




  
    <div class="article-entry" itemprop="articleBody">
       
  <p>This paper addresses several questions.</p>
<p>What is the backtracking algorithm? What are the techniques for solving problems related to backtracking algorithms? How do I learn backtracking algorithms? Is there a pattern to the backtracking algorithm code?</p>
<p>The backtracking algorithm is actually what we often call the <strong>DFS algorithm</strong>, which is essentially a violent exhaustive <strong>enumeration algorithm</strong>.</p>
<span id="more"></span>
<p><strong>Solving a backtracking problem is really a process of traversing a decision tree.</strong> You only need to think about 3 issues.</p>
<ol>
<li><p>The path: that is, the choices that have already been made.</p>
</li>
<li><p>The list of choices: that is, the choices you can currently make.</p>
</li>
<li><p>End condition: that is, the condition that you have reached the bottom of the decision tree and can no longer make a choice.</p>
</li>
</ol>
<p>If you don’t understand the explanation of these three terms, that’s fine, we’ll use the classic backtracking algorithm problems of ‘full permutation’ and ‘N queen problem’ later to help you understand what they mean, so for now you’ll stay with the impression.</p>
<h1 id="Framework-Code"><a href="#Framework-Code" class="headerlink" title="Framework Code"></a>Framework Code</h1><p>In terms of code, the framework of the backtracking algorithm:</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">result = []</span><br><span class="line"><span class="keyword">def</span> <span class="title function_">backtrack</span>(<span class="params">paths, choice_list</span>):</span><br><span class="line">    <span class="keyword">if</span> Meeting the ending conditions:</span><br><span class="line">        result.add(path)</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> choice <span class="keyword">in</span> choice_list:</span><br><span class="line">        make choices</span><br><span class="line">        backtrack(paths, choice_list)</span><br><span class="line">        undo choices</span><br></pre></td></tr></table></figure>
<p><strong>The core of this is the recursion inside the for loop, where you ‘make a choice’ before the recursive call and ‘undo the choice’ after the recursive call.</strong></p>
<p>What does it mean to select and deselect, and what is the underlying principle of this framework? Let’s go through the problem of ‘full permutation’ to clear up the confusion and explore the intricacies in detail!</p>
<h1 id="Ⅰ-Full-Permutation"><a href="#Ⅰ-Full-Permutation" class="headerlink" title="Ⅰ. Full Permutation"></a>Ⅰ. Full Permutation</h1><p>We have done maths problems with permutations in high school and we know that there are $n$ non-repeating numbers and that there are $n!$</p>
<p>PS: <strong>For the sake of simplicity and clarity, we are discussing permutations without repeating numbers.</strong></p>
<p>So how did we exhaust the full permutations then? If you are given three numbers <code>[1,2,3]</code>, you would not exhaust them in a random way.</p>
<p>First fix the first place as <code>1</code>, then the second place can be <code>2</code>, then the third place can only be <code>3</code>; then you can turn the second place into <code>3</code>, and the third place can only be <code>2</code>; then you can only change the first place into <code>2</code>, and then exhaust the last two places ……</p>
<p>In fact, this is the backtracking algorithm, which we use in high school without a teacher, or some students directly draw this backtracking tree as follows.</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic1.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">backtracking tree</div>
</center>

<p>Simply traverse the tree from the root and <strong>record the numbers on the path</strong>, which are in fact all the full permutations. We might <strong>call this tree the ‘decision tree’ of the backtracking algorithm.</strong></p>
<p><strong>Why do you call this a decision tree? Because you are actually making a decision at each node.</strong> Let’s say you are standing on the red node in the diagram below:</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic2.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">backtracking tree</div>
</center>

<p>You are now making a decision, either to choose the <code>1</code> branch or to choose the <code>3</code> branch. Why can you only choose between <code>1</code> and <code>3</code>? Because the branch <code>2</code> is behind you, a choice you have made before, and full permutation does not allow for repeated use of numbers.</p>
<p><strong>Now you can answer the first few terms-: <code>[2]</code> is the ‘path’, which records the choices you have already made; <code>[1,3]</code> is the ‘choice list’, which indicates the choices you can currently make; and the ‘end condition’ is the traversal to the bottom of the tree, in this case when the choice list is empty.</strong></p>
<p>If you understand these terms, you can <strong>use the ‘path’ and ‘choice’ lists as attributes of each node in the decision tree</strong>, the following diagram lists the attributes of several nodes:</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic3.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">attributes of several nodes</div>
</center>

<p><strong>The <code>backtrack</code> function we define is actually like a pointer that wanders around the tree, while maintaining the correct properties of each node, and whenever it reaches the bottom of the tree, its ‘path’ is a full alignment.</strong></p>
<p>Taking this a step further, how do you traverse a tree? This shouldn’t be too difficult. <strong>In fact, all kinds of search problems are in fact tree traversal problems</strong>, and the framework for traversing a multinomial tree is as follows.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> <span class="title function_">traverse</span><span class="params">(TreeNode root)</span> &#123;</span><br><span class="line">    <span class="keyword">for</span> (TreeNode child : root.childern)</span><br><span class="line">        <span class="comment">// Operations required for pre-order traversal</span></span><br><span class="line">        traverse(child);</span><br><span class="line">        <span class="comment">// Operations required for post-order traversal</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>And the so-called pre-order traversal and post-order traversal, they’re just two very useful points in time, as you’ll see if I draw you a diagram:</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic4.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">different traversal ways</div>
</center>

<p><strong>Pre-order traversal code is executed at the point in time before entering a node, and post-order traversal code is executed at the point in time after leaving a node.</strong></p>
<p>To recall what we said earlier, ‘path’ and ‘selection’ are properties of each node. And a function needs to properly maintain the properties of a node as it travels through the tree, it has to do something at these two particular times.</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic5.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">maintain the properties</div>
</center>

<p>Now, do you understand this core framework of the backtracking algorithm?</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> choice <span class="keyword">in</span> choice_list:</span><br><span class="line">    <span class="comment"># make a choice</span></span><br><span class="line">    <span class="comment"># remove this choice from choice_list</span></span><br><span class="line">    path.add(choice)</span><br><span class="line">    backtrack(path, choice_list)</span><br><span class="line">    <span class="comment"># Undo a choice</span></span><br><span class="line">    path.remove(choice)</span><br><span class="line">    <span class="comment"># add this choice into choice_list</span></span><br></pre></td></tr></table></figure>
<p>We can get the correct list of choices and paths for each node by simply <strong>making the choices before the recursion and undoing the choices just made after the recursion.</strong></p>
<p>Below, look directly at the full alignment code:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="comment">/* main function: Enter a set of non-repeating numbers and return their full alignment */</span></span><br><span class="line">List&lt;List&lt;Integer&gt;&gt; <span class="title function_">permute</span><span class="params">(<span class="type">int</span>[] nums)</span> &#123;</span><br><span class="line">    <span class="comment">// record「path」</span></span><br><span class="line">    LinkedList&lt;Integer&gt; track = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line">    backtrack(nums, track);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// path：recorded in track</span></span><br><span class="line"><span class="comment">// Select list: those elements of nums that do not exist in track</span></span><br><span class="line"><span class="comment">// End condition: all elements in nums are present in track</span></span><br><span class="line"><span class="keyword">void</span> <span class="title function_">backtrack</span><span class="params">(<span class="type">int</span>[] nums, LinkedList&lt;Integer&gt; track)</span> &#123;</span><br><span class="line">    <span class="comment">// Trigger end conditions</span></span><br><span class="line">    <span class="keyword">if</span> (track.size() == nums.length) &#123;</span><br><span class="line">        res.add(<span class="keyword">new</span> <span class="title class_">LinkedList</span>(track));</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="comment">// Excluding unlawful options</span></span><br><span class="line">        <span class="keyword">if</span> (track.contains(nums[i]))</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        <span class="comment">// Make a choice</span></span><br><span class="line">        track.add(nums[i]);</span><br><span class="line">        <span class="comment">// Go to the next level of the decision tree</span></span><br><span class="line">        backtrack(nums, track);</span><br><span class="line">        <span class="comment">// Undo choice</span></span><br><span class="line">        track.removeLast();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>Instead of explicitly recording the 「selection list」, we have derived the current selection list from <code>nums</code> and <code>track</code>.</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic6.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">derived the current selection list</div>
</center>

<p>At this point, we have explained the underlying principle of the backtracking algorithm in detail through the full permutation problem. Of course, this algorithm is not very efficient in solving full permutations, as it requires an $O(N)$ time complexity to use the <code>contains</code> method on a linked table. There are better ways to achieve this by swapping elements, but they are harder to understand, so I won’t write about them here, so you can search for them yourself if you are interested.</p>
<p>However, it is important to note that no matter how it is optimised, it fits into the backtracking framework and the time complexity cannot be lower than $O(N!)$ because exhausting the whole decision tree is unavoidable. <strong>This is a feature of backtracking algorithms; unlike dynamic programming where there are overlapping subproblems that can be optimised, backtracking algorithms are purely violent exhaustive enumeration and the complexity is generally very high.</strong></p>
<p>Once the full permutation problem is understood, it is straightforward to apply the backtracking algorithm framework, and the following is a brief look at the N queen problem.</p>
<h1 id="Ⅱ-N-queen-problem"><a href="#Ⅱ-N-queen-problem" class="headerlink" title="Ⅱ. N queen problem"></a>Ⅱ. N queen problem</h1><p>This is a classic problem, to explain it simply: you are given an $N \times N$ board, and you are asked to place $N$ queens so that they cannot attack each other.</p>
<p>PS: Queens can attack any unit in the same row, column, top-left, bottom-left, top-right and bottom-four directions.</p>
<p>This problem is essentially like the full permutation problem, where each level of the decision tree represents each row on the board; each node can make the choice of placing a queen in any column of that row.</p>
<p>Apply code framework directly :</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;vector&lt;string&gt;&gt; res;</span><br><span class="line"></span><br><span class="line"><span class="comment">/* Enter the board edge length &#x27;n&#x27; and return all legal placements */</span></span><br><span class="line">vector&lt;vector&lt;string&gt;&gt; <span class="title function_">solveNQueens</span><span class="params">(<span class="type">int</span> n)</span> &#123;</span><br><span class="line">    <span class="comment">// &#x27;.&#x27; means empty, &#x27;Q&#x27; means queen, initializing empty board</span></span><br><span class="line">    vector&lt;string&gt; <span class="title function_">board</span><span class="params">(n, string(n, <span class="string">&#x27;.&#x27;</span>)</span>);</span><br><span class="line">    backtrack(board, <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// Path: all rows in the &#x27;board&#x27; less than &#x27;row&#x27; have successfully placed queens</span></span><br><span class="line"><span class="comment">// selection list: all columns in row &#x27;row&#x27; are choices for placing the queen</span></span><br><span class="line"><span class="comment">// End condition: &#x27;row&#x27; exceeds the last row of &#x27;board&#x27;</span></span><br><span class="line"><span class="keyword">void</span> <span class="title function_">backtrack</span><span class="params">(vector&lt;string&gt;&amp; board, <span class="type">int</span> row)</span> &#123;</span><br><span class="line">    <span class="comment">// Trigger end conditions</span></span><br><span class="line">    <span class="keyword">if</span> (row == board.size()) &#123;</span><br><span class="line">        res.push_back(board);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> board[row].size();</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">col</span> <span class="operator">=</span> <span class="number">0</span>; col &lt; n; col++) &#123;</span><br><span class="line">        <span class="comment">// Exclusion of unlawful options</span></span><br><span class="line">        <span class="keyword">if</span> (!isValid(board, row, col)) </span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        <span class="comment">// Make a choice</span></span><br><span class="line">        board[row][col] = <span class="string">&#x27;Q&#x27;</span>;</span><br><span class="line">        <span class="comment">// Go to the next line of decision making</span></span><br><span class="line">        backtrack(board, row + <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// Undo choice</span></span><br><span class="line">        board[row][col] = <span class="string">&#x27;.&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The main code in this section is actually similar to the full alignment problem, and the implementation of the <code>sValid</code> function is very simple:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/* Is it possible to place queens in &#x27;board[row][col]&#x27;  */</span></span><br><span class="line">bool <span class="title function_">isValid</span><span class="params">(vector&lt;string&gt;&amp; board, <span class="type">int</span> row, <span class="type">int</span> col)</span> &#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> board.size();</span><br><span class="line">    <span class="comment">// Check if the columns have conflicting queens</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (board[i][col] == <span class="string">&#x27;Q&#x27;</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// Check the top right for conflicting queens</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> row - <span class="number">1</span>, j = col + <span class="number">1</span>; </span><br><span class="line">            i &gt;= <span class="number">0</span> &amp;&amp; j &lt; n; i--, j++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (board[i][j] == <span class="string">&#x27;Q&#x27;</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// Check the top left for conflicting queens</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> row - <span class="number">1</span>, j = col - <span class="number">1</span>;</span><br><span class="line">            i &gt;= <span class="number">0</span> &amp;&amp; j &gt;= <span class="number">0</span>; i--, j--) &#123;</span><br><span class="line">        <span class="keyword">if</span> (board[i][j] == <span class="string">&#x27;Q&#x27;</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The <code>backtrack</code> function is still like a pointer that wanders through the decision tree, with <code>row</code> and <code>col</code> representing the positions traversed by the function, and the <code>isValid</code> function pruning out the unqualified cases:</p>
<center>
  <img style="border-radius: 0.3125em;
  box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
  src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed/blog/DFSFramework/pic7.png" width='70%'>
  <br>
  <div style="color:orange; border-bottom: 1px solid #d9d9d9;
  display: inline-block;
  color: #999;
  padding: 2px;">pruning out the unqualified cases</div>
</center>

<p>If you were given such a large piece of solution code straight away, it might be confusing. But now that you understand the framework of the backtracking algorithm, what’s so hard to understand? It’s just a matter of changing the way you make choices and eliminating illegitimate choices, and once you have the framework in mind, you’re left with a small problem.</p>
<p>When <code>N = 8</code>, it’s the eight queens problem. The mathematician Gauss has never been able to count the number of possible ways to place the eight queens problem in his lifetime, but our algorithm can work out all the possible outcomes in just one second.</p>
<p>But it’s not really Gauss’s fault. The complexity of the problem is very high indeed, and looking at our decision tree, despite the <code>isValid</code> function pruning, the worst time complexity is still $O(N^{N+1})$ and cannot be optimised. If <code>N = 10</code>, the computation is already time-consuming.</p>
<p><strong>There are times when we do not want to get all the legal answers, but only one answer.</strong> For example, in the algorithm for solving Sudoku, the complexity of finding all solutions is too high, and finding just one solution is fine.</p>
<p>In fact it is particularly simple, with a slight modification to the code of the backtracking algorithm.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// The function returns `true` when it finds an answer</span></span><br><span class="line">bool <span class="title function_">backtrack</span><span class="params">(vector&lt;string&gt;&amp; board, <span class="type">int</span> row)</span> &#123;</span><br><span class="line">    <span class="comment">// Trigger end conditions</span></span><br><span class="line">    <span class="keyword">if</span> (row == board.size()) &#123;</span><br><span class="line">        res.push_back(board);</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    ...</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">col</span> <span class="operator">=</span> <span class="number">0</span>; col &lt; n; col++) &#123;</span><br><span class="line">        ...</span><br><span class="line">        board[row][col] = <span class="string">&#x27;Q&#x27;</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (backtrack(board, row + <span class="number">1</span>))</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        </span><br><span class="line">        board[row][col] = <span class="string">&#x27;.&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>With this modification, any subsequent recursive exhaustion of the <code>for</code> loop will be blocked as soon as an answer is found. Perhaps you could write an algorithm for solving Sudoku with a slight modification to the code framework of the N Queen problem?</p>
<h1 id="Ⅲ-Conclusion"><a href="#Ⅲ-Conclusion" class="headerlink" title="Ⅲ. Conclusion"></a>Ⅲ. Conclusion</h1><p>The backtracking algorithm is a multinomial tree traversal problem, the key is to do some operations at the location of the preorder traversal and postorder traversal, the algorithm framework is as follows:</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">backtrack</span>(<span class="params">...</span>):</span><br><span class="line">    <span class="keyword">for</span> choice <span class="keyword">in</span> choice_list:</span><br><span class="line">        <span class="comment"># make choices</span></span><br><span class="line">        backtrack(...)</span><br><span class="line">        <span class="comment"># Undo choices</span></span><br></pre></td></tr></table></figure>
<p><strong>When writing the <code>backtrack</code> function, you need to maintain the ‘path’ travelled and the ‘list of choices’ that you can currently make, and when the ‘end condition’ is triggered, the ‘path’ is recorded in the result set.</strong></p>
<p>If you think about it, isn’t the backtracking algorithm a bit like dynamic programming? As we have emphasized many times in the dynamic programming series, the three points that need to be clarified in dynamic programming are “state”, “choice” and “base case”, does this not correspond to the “path” travelled, the current “choice list” and the “end condition”?</p>
<p>In a way, the violent solution phase of dynamic programming is a backtracking algorithm. It’s just that some problems have the nature of overlapping subproblems, and can be optimized with dp tables or memoization to prune the recursive tree significantly, which becomes dynamic programming. In today’s two problems, however, there are no overlapping subproblems, which means that the problem is a backtracking algorithm, and a very high complexity is inevitable.</p>
 
      <!-- reward -->
      
      <div id="reword-out">
        <div id="reward-btn">
          打赏
        </div>
      </div>
      
    </div>
    

    <!-- copyright -->
    
    <div class="declare">
      <ul class="post-copyright">
        <li>
          <i class="ri-copyright-line"></i>
          <strong>版权声明： </strong>
          
          本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
          
        </li>
      </ul>
    </div>
    
    <footer class="article-footer">
       
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=https://blog.shimmerjordan.eu.org/2021/08/07/DFSFramework/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>  
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Algorithm/" rel="tag">Algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Backtracking/" rel="tag">Backtracking</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DFS/" rel="tag">DFS</a></li></ul>

    </footer>
  </div>

   
  <nav class="article-nav">
    
      <a href="/2021/11/01/clever-use-of-set/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            Clever use of set
          
        </div>
      </a>
    
    
      <a href="/2021/08/02/LC743-shortestCircuit_mapsStorage/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">Five shortest-circuit algorithms &amp; two ways to store maps</div>
      </a>
    
  </nav>

   
<!-- valine评论 -->
<div id="vcomments-box">
  <div id="vcomments"></div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js"></script>
<script>
  new Valine({
    el: "#vcomments",
    app_id: "StYfTMDp78X0EltFR16ve2q5-gzGzoHsz",
    app_key: "G4RPxRpXG6RwdfpnJefOSnyy",
    path: window.location.pathname,
    avatar: "wavatar",
    placeholder: "ヾﾉ≧∀≦)o来啊，快活啊!",
    recordIP: true,
  });
  const infoEle = document.querySelector("#vcomments .info");
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
    infoEle.childNodes.forEach(function (item) {
      item.parentNode.removeChild(item);
    });
  }
</script>
<style>
  #vcomments-box {
    padding: 5px 30px;
  }

  @media screen and (max-width: 800px) {
    #vcomments-box {
      padding: 5px 0px;
    }
  }

  #vcomments-box #vcomments {
    background-color: #fff;
  }

  .v .vlist .vcard .vh {
    padding-right: 20px;
  }

  .v .vlist .vcard {
    padding-left: 10px;
  }
</style>

 
   
   
<!-- minivaline评论 -->
<div id="mvcomments-box">
  <div id="mvcomments"></div>
</div>
<script src="https://cdn.jsdelivr.net/npm/minivaline@latest"></script>
<script>
    new MiniValine(Object.assign({"enable":true,"mode":"DesertsP","placeholder":"Write a Comment","math":true,"md":true,"enableQQ":true,"NoRecordIP":false,"visitor":true,"maxNest":6,"pageSize":6,"adminEmailMd5":"de8a7aa53d07e6b6bceb45c64027763d","tagMeta":["管理员","小伙伴","访客"],"master":["de8a7aa53d07e6b6bceb45c64027763d"],"friends":["b5bd5d836c7a0091aa8473e79ed4c25e","adb7d1cd192658a55c0ad22a3309cecf","3ce1e6c77b4910f1871106cb30dc62b0","cfce8dc43725cc14ffcd9fb4892d5bfc"],"lang":null,"emoticonUrl":["https://cdn.jsdelivr.net/npm/alus@latest","https://cdn.jsdelivr.net/gh/MiniValine/qq@latest","https://cdn.jsdelivr.net/gh/MiniValine/Bilibilis@latest","https://cdn.jsdelivr.net/gh/MiniValine/tieba@latest","https://cdn.jsdelivr.net/gh/MiniValine/twemoji@latest","https://cdn.jsdelivr.net/gh/MiniValine/weibo@latest"]}, {
	  el: '#mvcomments',
    }));
  const infoEle = document.querySelector('#mvcomments .info');
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
      infoEle.childNodes.forEach(function (item) {
          item.parentNode.removeChild(item);
      });
  }
</script>
<style>
	#mvcomments-box {
		padding: 5px 30px;
	}
	@media screen and (max-width: 800px) {
		#mvcomments-box {
		  padding: 5px 0px;
		}
	}
	.darkmode .MiniValine *{
		color: #f1f1f1!important;
	}
	.darkmode .commentTrigger{
		background-color: #403e3e !important;
	  }
	.darkmode .MiniValine .vpage .more{
		background: #21232F
	}
	.darkmode img{
		filter: brightness(30%)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:before{
		background: linear-gradient(180deg, rgba(246,246,246,0), rgba(0,0,0,0.9))
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:after{
		background: rgba(0,0,0,0.9)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment pre{
		background: #282c34
		border: 1px solid #282c34
	}
	.darkmode .MiniValine .vinputs-area .textarea-wrapper textarea{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper input{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .vextra-area .vsmile-icons{
		background: transparent;
	}
	.darkmode .MiniValine .vinputs-wrap{
		border-color: #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-wrap:hover{
		border: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper{
		border-bottom: 1px dashed #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper:hover{
		border-bottom: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vbtn{
		background-color: transparent!important;
	}
	.darkmode .MiniValine .vbtn:hover{
		border: 1px dashed #2196f3;
	}
</style>

    
</article>

</section>
      <footer class="footer">
  <div class="outer">
    <ul>
      <li>
        Copyrights &copy;
        2019-2024
        <i class="ri-heart-fill heart_icon"></i> 鞠桥丹-QIAODAN JU
      </li>
    </ul>
    <ul>
      <li>
        
        
        
        由 <a href="https://hexo.io" target="_blank">Hexo</a> 强力驱动
        <span class="division">|</span>
        主题 - <a href="https://github.com/Shen-Yu/hexo-theme-ayer" target="_blank">Ayer</a>
        
      </li>
    </ul>
    <ul>
      <li>
        
        
        <span>
  <span><i class="ri-user-3-fill"></i>访问人数:<span id="busuanzi_value_site_uv"></span></s>
  <span class="division">|</span>
  <span><i class="ri-eye-fill"></i>浏览次数:<span id="busuanzi_value_page_pv"></span></span>
</span>
        
      </li>
    </ul>
    <ul>
      
    </ul>
    <ul>
      
    </ul>
    <ul>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s4.cnzz.com/z_stat.php?id=1279035150&amp;web_id=1279035150'></script>
        
      </li>
    </ul>
  </div>
</footer>
      <div class="float_btns">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>

<div class="todark" id="todark">
  <i class="ri-moon-line"></i>
</div>

      </div>
    </main>
    <aside class="sidebar on">
      <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="丛烨-shimmerjordan"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">Home</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/archives">Catalogue</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">Tags</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E9%9A%8F%E7%AC%94/">Essay</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/categories">Archives</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/friends">Friends</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/01/18/about">About</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="搜索">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
    </aside>
    <script>
      if (window.matchMedia("(max-width: 768px)").matches) {
        document.querySelector('.content').classList.remove('on');
        document.querySelector('.sidebar').classList.remove('on');
      }
    </script>
    <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯蓝莓汁吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
    
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/lazyload.min.js"></script>

<!-- Tocbot -->


<script src="/js/tocbot.min.js"></script>

<script>
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer: 'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto'
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js"></script>

<script src="/dist/main.js"></script>

<!-- ImageViewer -->

<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>

<!-- MathJax -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
  var ayerConfig = {
    mathjax: true
  }
</script>

<!-- Katex -->

<!-- busuanzi  -->


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<!-- ClickLove -->


<script src="/js/clickLove.js"></script>


<!-- ClickBoom1 -->

<!-- ClickBoom2 -->

<!-- CodeCopy -->


<link rel="stylesheet" href="/css/clipboard.css">

<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  function wait(callback, seconds) {
    var timelag = null;
    timelag = window.setTimeout(callback, seconds);
  }
  !function (e, t, a) {
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '<i class="ri-file-copy-2-line"></i><span>COPY</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      $(".article pre code").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });
      clipboard.on('success', function(e) {
        let $btn = $(e.trigger);
        $btn.addClass('copied');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-checkbox-circle-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPIED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-checkbox-circle-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
      clipboard.on('error', function(e) {
        e.clearSelection();
        let $btn = $(e.trigger);
        $btn.addClass('copy-failed');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-time-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPY FAILED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-time-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
    }
    initCopyCode();
  }(window, document);
</script>


<!-- CanvasBackground -->


<script src="/js/dz.js"></script>



    
  </div>
</body>

</html>